package algorithmlearn.sort;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
       //1.
        int[] array = {3, 1, 4, 2, 3, 5};
        int[] ints = quickSort(array, 0, array.length - 1);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + "  ");
        }

       //2/
        int[] array2 = {3, 1, 4, 2, 3, 5};
        int[] ints2 = quickSort2(array2, 0, array2.length - 1);
        for (int i = 0; i < ints2.length; i++) {
            System.out.print(ints[i] + "  ");
        }
    }

    /**
     * 快速排序方法2  双路快排，2个哨兵
     *
     * @param array
     * @param left  index
     * @param right index
     * @return
     */
    public static int[] quickSort2(int[] array, int left, int right) {
        if (array == null || array.length < 2 || left >= right)
            return array;
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i != j) { //顺序很重要，要先从右边开始找
            /*
            i和j相遇的时候会和基准值进行交换，交换的时候需要基准值和比它小的值交换才行，所以只有从右侧先开始，
            在找到比基准值小的时候停下，然后从左边开始找，如果i没有找到比基准值大的，就会和j相遇，然后基准值就会和相遇处的值进行交换。所以必须从右边先开始。
             */
            while (array[j] >= pivot && j > i) {
                j--;
            }
            while (array[i] <= pivot && i < j) {//再找右边的
                i++;
            }
            if (i < j) {
                swap(array, i, j);
            }
        }
        //最终将基准数归位
        array[left] = array[i];
        array[i] = pivot;
        quickSort2(array, left, i - 1);//继续处理左边的，这里是一个递归的过程
        quickSort2(array, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
        return array;
    }


    /**
     * 快速排序方法  单路快排，挖坑法
     *
     * @param array
     * @param start index
     * @param end   index
     * @return
     */
    public static int[] quickSort(int[] array, int start, int end) {
        if (array == null || array.length < 2 || start < 0 || end >= array.length || start > end) return array;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start)
            quickSort(array, start, smallIndex - 1);
        if (smallIndex < end)
            quickSort(array, smallIndex + 1, end);
        return array;
    }

    /**
     * 快速排序算法——partition
     *
     * @param array
     * @param start index
     * @param end   index
     * @return
     */
    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        }

        return smallIndex;
    }

    /**
     * 交换数组内两个元素
     *
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
